package org.KeyCrafter.ds.skiplist;

import java.util.Iterator;

public class ZSkipList implements SkipList{

    /**
     * 定义节点内容
     */
    private static class ZSkipListNode implements SkipList.Node{
        // 存储数据对象
        Object obj;

        // 用于存储排序的分值
        double score;

        // 后退指针
        ZSkipListNode backward;

        @Override
        public double getScore() {
            return score;
        }

        @Override
        public Object getObject() {
            return obj;
        }

        /**
         * 1. level 是一个柔性数组，每个节点的数组长度不一样，
         *    在生成跳跃表节点时，随机生成一个 1 ~ 64 的值，值越大出现概率越低。
         * 2. level数组包含两个元素：
         *      a. forward 前进指针
         *          指向本层下一个节点，最终指向 null
         *      b. span 跨度
         *          指向的节点与本节点之间的元素个数
         */
        static class ZSkipListLevel{
            // 前进指针
            ZSkipListNode forward;

            // 跨度
            int span;
        }

        // 定义层
        ZSkipListLevel[] level;

        // 初始化构造器
        public ZSkipListNode(int level, double score, Object obj){
            // 设置层数大小
            ZSkipListLevel[] skipListLevels = new ZSkipListLevel[level];
            this.level = skipListLevels;

            // 设置属性
            this.score = score;
            this.obj = obj;
        }
        // 为了能被 kryo 复制，无参构造器
        public ZSkipListNode() {
        }
    }

    /**
     * 1. 定义表头节点和尾节点
     * 2. 注意头节点中不存储仍和 member和 score值，obj为 null，score为 0; 也不计入跳表总长度。
     */
    ZSkipListNode header;
    ZSkipListNode tail;

    // 定义表节点数量(注意：不包括头节点)
    long length;

    // 表示跳表高度
    int level;

    // 创建跳表
    public ZSkipList() {
        // 设置高度和起始层数

        this.length = 0;
        this.level = 1;
        // 创建初始化具有64层的头节点
        this.header = new ZSkipListNode(ZSKIPLIST_MAXLEVEL, 0, null);
        // 头节点每层都有一个level软列表
        // 头节点每层forward指向null
        // 头节点层数是0
        for (int i = 0; i < ZSKIPLIST_MAXLEVEL; i++){
            this.header.level[i] = new ZSkipListNode.ZSkipListLevel();
            this.header.level[i].forward = null;
            this.header.level[i].span = 0;
        }
        // 回调节点和尾节点都为null
        this.header.backward = null;
        this.tail = null;
    }

    /**
     * 1. 为了找到要更新的节点，我们需要以下两个长度为64的数组来辅助操作
     *      a. update[]: 插入节点时，需要更新被插入节点每层的前一个节点。
     *          由于每层更新结点不一样，所以需要将每层需要更新的节点记录在update[i]中
     *      b. rank[]: 记录当前层从header节点到update[i]节点所经历的步长，
     *          更新 update[i]的span和设置新插入节点的span时使用
     * 2.
     * @param score
     * @param obj
     * @return
     */
    @Override
    public Node insert(double score, Object obj) {
        ZSkipListNode[] update = new ZSkipListNode[ZSKIPLIST_MAXLEVEL];
        int[] rank = new int[ZSKIPLIST_MAXLEVEL];
        // 定义一个节点
        ZSkipListNode x;
        int i, level;

        // 在各层查找节点插入位置
        x = this.header;
        for (i = this.level - 1; i>= 0; i--){
            // 如果 i 不是 zsl->level-1 层
            // 那么 i 层的起始 rank 值为 i+1 层的rank值
            // 各层rank的rank值一层层累积
            // 最终 rank[0] 的值加一就是新节点的前置节点的排位
            // rank[0] 会成为计算span和rank的值基础
            // 这里初始化rank
            rank[i] = i == (this.level - 1) ? 0 : rank[i + 1];

            // 沿着前进指针遍历跳跃表
            // 当前分支小于目标分值或者分值相同但是对象字典小于目标
            while (x.level[i].forward != null &&
                    (x.level[i].forward.score < score ||
                            (x.level[i].forward.score == score &&
                                    compareStringObjects(x.level[i].forward.obj, obj) < 0))){
                // 记录跨越节点数
                rank[i] += x.level[i].span;

                // 移动到下一节点指针
                x = x.level[i].forward;
            }
            // 记录将要和新节点相连的节点
            // 新节点在i层，指向该节点第i层前进节点
            update[i] = x;
        }

        /**
         * insert() 的调用者会确保同分值，且同成员元素不会再出现
         * 所以不需要进一步检查，直接创建新元素
         */
        // 由于插入节点的高度是随机的，我们需要调整高度
        level = randomLevel();

        // 如果新节点的层数比表中其他节点的层数都要大
        // 那么初始化header节点中未使用的这层，并将他记录到 update 数组中
        // 将来也指向新节点
        if (level > this.level){
            // 初始化未使用层
            for (i = this.level; i < level; i++){
                rank[i] = 0;
                update[i] = this.header;
                update[i].level[i].span = (int) this.length;
            }
            this.level = level;
        }

        // 此前代码得到了插入位置，并且调整了高度，
        // 接下来我们就要创建新节点，并且插入到跳跃表中
        x = new ZSkipListNode(level, score, obj);
        // 将前面记录的指针指向新节点，并做对应设置
        for (i = 0; i < level; i++){
            x.level[i] = new ZSkipListNode.ZSkipListLevel();
            // 设置新节点的 forward 指针
            x.level[i].forward = update[i].level[i].forward;

            // 将沿途记录各个节点的 forward 指针指向新节点
            update[i].level[i].forward = x;

            // 计算新节点跨越节点数量
            x.level[i].span = update[i].level[i].span - (rank[0] - rank[i]);

            // 更新新节点插入之后，沿途节点的span值
            // 其中的 +1 计算的是新节点
            update[i].level[i].span = (rank[0] - rank[i]) + 1;
        }
        // 由于新增了节点，所以未接触节点的跨度也要增加1，这些节点直接从表头指向新节点
        for (i = level; i < this.level; i++){
            update[i].level[i].span++;
        }

        // 调整新节点的后退指针
        x.backward = (update[0] == this.header) ? null : update[0];
        // 调整第1层
        if (x.level[0].forward != null){
            x.level[0].forward.backward = x;
        }else {
            this.tail = x;
        }

        return x;
    }

    /**
     * 返回一个随机值，作为跳跃表层数
     *
     * 返回值介于 1 和 ZSKIPLIST_MAXLEVEL 之间(包含 ZSKIPLIST_MAXLEVEL)，
     * 根据随机算法所使用的幂次定律，越大的值生成几率越小
     * @return
     */
    private int randomLevel() {
        int level = 1;
        while(Math.random() < ZSKIPLIST_P){
            level += 1;
        }
        return (Math.min(level, ZSKIPLIST_MAXLEVEL));
    }

    // 比较两个字符串大小
    // 相同返回0
    private int compareStringObjects(Object a, Object b){
        assert a instanceof String && b instanceof String;
        String a1 = (String) a;
        String b1 = (String) b;
        return a1.compareTo(b1);
    }

    /**
     * 查找包含给定分值和成员对象的节点在跳跃表中的排位
     * 如果没有包含给定分值和成员对象的节点，返回0，否则返回排位
     * 注意，由于跳跃表表头也算在内，所以返回排位以1起步
     *
     * @param score
     * @param obj
     * @return
     */
    @Override
    public long getRank(double score, Object obj) {
        ZSkipListNode x;
        long rank = 0;

        //  遍历整个跳表
        x = this.header;
        // 遍历层
        for (int i = this.level - 1; i >= 0; i--){
            // 遍历节点并对比元素
            while (x.level[i].forward != null &&
                    (x.level[i].forward.score < score ||
                            // 对比分值
                            (x.level[i].forward.score == score &&
                                    // 对比成员
                                    compareStringObjects(x.level[i].forward.obj, obj) <= 0))){
                // 累积跨越的节点数量
                rank += x.level[i].span;

                // 沿着前进指针遍历跳表
                x = x.level[i].forward;
            }

            // 必须确保不仅分值相等，而且成员对象也要相等
            if (x.obj != null && equalStringObjects(x.obj, obj)){
                return rank;
            }
        }
        // 未找到
        return 0;
    }

    private boolean equalStringObjects(Object a, Object b) {
        assert a instanceof String && b instanceof String;
        return a.equals(b);
    }

    /**
     * 从跳表 zsl 中删除包含指定节点 score 并且带有指定对象的节点
     * 实现方法和insert类似
     * @param score
     * @param obj
     * @return
     */
    @Override
    public int delete(double score, Object obj) {
        ZSkipListNode[] update = new ZSkipListNode[ZSKIPLIST_MAXLEVEL];
        ZSkipListNode x;
        // 遍历跳表，查询目标节点，并且记录跨度
        x = this.header;
        for (int i = this.level - 1; i >= 0; i--) {
            // 遍历跳跃表的复杂度为 T_wrost = O(N), T_avg = O(log N)
            while (x.level[i].forward != null &&
                    (x.level[i].forward.score < score ||
                            // 比对分值
                            (x.level[i].forward.score == score &&
                                    // 比对对象，T = O(N)
                                    compareStringObjects(x.level[i].forward.obj, obj) < 0))) {
                // 沿着前进指针移动
                x = x.level[i].forward;
            }
            // 记录沿途节点
            update[i] = x;
        }

        // 检查找到的 x，如果他的分值和对象都相同，删除。
        // 此时若 x 不为null，则x 的forward 要么 score比目标值大
        x = x.level[0].forward;
        if (x != null && x.score == score && equalStringObjects(x.obj, obj)) {
            deleteNode(x, update);
        } else {
            // 没有找到
            return 0;
        }
        return 0;
    }

    /**
     * 真实处理节点删除的函数
     * @param x
     * @param update
     */
    private void deleteNode(ZSkipListNode x, ZSkipListNode[] update) {
        // 更新所有和被删除节点 x 有关节点的指针，并且更新关系
        for (int i = 0; i < this.level; i++){
            if (update[i].level[i].forward == x){
                update[i].level[i].span += x.level[i].span - 1;
                update[i].level[i].forward = x.level[i].forward;
            }else {
                // 后面节点，跨度减1
                update[i].level[i].span -= 1;
            }
        }

        // 更新被删除节点x的前进和后退指针
        if (x.level[0].forward != null){
            x.level[0].forward.backward = x.backward;
        }else {
            this.tail = x.backward;
        }

        // 更新跳表最大层数(只有在被删除节点是跳表中最高节点时才执行)
        while(this.level > 1 && this.header.level[this.level - 1].forward == null){
            this.level--;
        }
        //节点计数器减一
        this.length--;
    }

    /**
     * 根据排位在跳跃表中查找元素。排位起始值为1
     * 查找成功返回跳表节点，否则返回null
     * @param rank
     * @return
     */
    @Override
    public Node getElementByRank(long rank) {
        ZSkipListNode x;
        long traversed = 0;
        x = this.header;
        for (int i = this.level - 1; i >= 0; i--) {
            // 遍历跳跃表并累积越过的节点数量
            while (x.level[i].forward != null &&
                    (traversed + x.level[i].span) <= rank) {
                traversed += x.level[i].span;
                x = x.level[i].forward;
            }

            // 如果越过的节点数量已经等于 rank
            // 那么说明已经到达要找的节点
            if (traversed == rank) {
                return x;
            }
        }
        // 没找到目标节点
        return null;
    }

    @Override
    public boolean isInRange(RangeSpec range) {
        ZSkipListNode x;
        // 先排除总为空的范围值
        if (range.getMin() > range.getMax() ||
                (range.getMin() == range.getMax() && range.isMinex())){
            return false;
        }

        // 检查最大分值(最大值在尾部)
        x = this.tail;
        if (x == null || !valueGteMin(x.score, range)) return false;

        // 检查最小分值(最小值在header下一个)
        x = this.header.level[0].forward;
        if (x == null || !valueLteMax(x.score, range)) return false;

        return true;
    }

    /**
     * 检测score是否小于等于最大数值
     * 返回true表示是
     * @param score
     * @param spec
     * @return
     */
    private boolean valueLteMax(double score, RangeSpec spec) {
        return spec.isMaxex() ? (score < spec.getMax()) : (score <= spec.getMax());
    }

    /**
     * 检测score是否大于等于最小数值
     * 返回true表示是
     * @param score
     * @param spec
     * @return
     */
    private boolean valueGteMin(double score, RangeSpec spec) {
        return spec.isMinex() ? (score > spec.getMin()) : (score >= spec.getMin());
    }

    /**
     * 返回 zsl跳表中第一个分值符合range指定范围的节点
     * 如果没有返回null
     * @param range
     * @return
     */
    @Override
    public Node firstInRange(RangeSpec range) {
        ZSkipListNode x;
        if (!isInRange(range)) return null;

        // 遍历跳表，查询符合条件的 min节点
        x = this.header;
        for (int i = this.level - 1; i >= 0 ; i--) {
            while (x.level[i].forward != null &&
                    !valueGteMin(x.level[i].forward.score,range)) {
                x = x.level[i].forward;
            }
        }
        x = x.level[0].forward;
        assert x != null;

        // 检查节点是否符合范围的 max 项
        if (!valueLteMax(x.score,range)) return null;

        return x;
    }

    /**
     * 返回 zsl 中最后一个分值符合 range 中指定范围的节点
     * 若没有符合条件节点，返回null
     *
     * @param range
     * @return
     */
    @Override
    public Node lastInRange(RangeSpec range) {
        ZSkipListNode x;
        // 先总体校验是否存在满足范围条件节点
        if (!isInRange(range)) return null;

        // 遍历跳表节点，查找符合范围的 最后一个即 max节点
        x = this.header;
        for (int i = this.level - 1; i >= 0; i++){
            // 在范围内遍历该层
            while(x.level[i].forward != null &&
                    (valueLteMax(x.level[i].forward.score, range))){
                x = x.level[i].forward;
            }
        }

        // x经过valueLteMax控制，不能为 null
        assert x != null;

        // 检查节点是否符合范围的 min 项
        if (!valueGteMin(x.score, range)) return null;

        return x;
    }

    /**
     * 1. 删除所有在给定范围内的分值节点
     * 2. 由于max和min节点包含在范围内，所有会删除 >= min, <= max 节点
     * 3. 由于redis中 跳表和压缩列表都是dict的一种实现，最终使用哪种会在后续进行判断
     *      所以需要在二者同时删除
     * @param range
     * @return 删除节点数量
     */
    @Override
    public long deleteRangeByScore(RangeSpec range) {
        ZSkipListNode[] update = new ZSkipListNode[ZSKIPLIST_MAXLEVEL];
        ZSkipListNode x;
        long removed = 0;

        // 记录所有和被删除节点有关的节点
        x = this.header;
        for (int i = this.level - 1; i >= 0; i--) {
            while (x.level[i].forward != null && (range.isMinex() ?
                    x.level[i].forward.score <= range.getMin() :
                    x.level[i].forward.score < range.getMin())) {
                x = x.level[i].forward;
            }
            update[i] = x;
        }

        // 定位到给定范围开始的第一个节点
        x = x.level[0].forward;

        // 删除范围中的所有节点
        while (x != null &&
                (range.isMaxex() ? x.score < range.getMax() : x.score <= range.getMax())){
            // 记录下个节点指针
            ZSkipListNode next = x.level[0].forward;
            deleteNode(x, update);
            //todo 字典删除
            removed++;
            x = next;
        }
        return removed;
    }

    /**
     * 从跳表种删除所有在给定排位范围内的节点
     * start 和 end 都包含在内
     * @param start
     * @param end
     * @return
     */
    @Override
    public long deleteRangeByRank(int start, int end) {
        ZSkipListNode[] update = new ZSkipListNode[ZSKIPLIST_MAXLEVEL];
        ZSkipListNode x;
        // 定义排位rank计数器和删除数量计数器
        long traversed = 0, removed = 0;

        // 遍历所有节点
        x = this.header;
        for (int i = this.level - 1; i >= 0; i--) {
            while (x.level[i].forward != null && (traversed + x.level[i].span) < start) {
                traversed += x.level[i].span;
                x = x.level[i].forward;
            }
            update[i] = x;
        }

        // 移动到排位的起始的第一个节点
        traversed++;
        x = x.level[0].forward;

        // 删除所有在给定排位范围内的节点
        while (x != null && traversed <= end) {

            // 记录下一节点的指针
            ZSkipListNode next = x.level[0].forward;

            // 从跳跃表中删除节点
            deleteNode(x, update);
            // 删除计数器增一
            removed++;

            // 排位计数器增一
            traversed++;

            // 处理下个节点
            x = next;
        }

        // 返回被删除节点的数量
        return removed;
    }


    @Override
    public Iterator<Node> iterator(boolean revers) {
        return new ZSkipListIterator(revers);
    }

    private class ZSkipListIterator implements Iterator<Node> {
        boolean revers;
        ZSkipListNode ln;
        public ZSkipListIterator(boolean revers) {
            this.revers = revers;
            if (revers) {
                ln = ZSkipList.this.tail;
            } else {
                ln = ZSkipList.this.header.level[0].forward;
            }
        }
        @Override
        public boolean hasNext() {
            return ln != null;
        }

        @Override
        public ZSkipListNode next() {
            if (ln == null) {
                return null;
            }
            ZSkipListNode pre = ln;
            ln = revers ? ln.backward : ln.level[0].forward;
            return pre;
        }
    }

    private class ZSkipListRankIterator extends ZSkipListIterator{
        public ZSkipListRankIterator(long rank, boolean revers) {
            super(revers);
            // 如果rank 不大于1，就相当于返回了一个父迭代器
            if (rank > 1) {
                ln = (ZSkipListNode) ZSkipList.this.getElementByRank(rank);
            }
        }
    }


    @Override
    public Iterator<Node> getIteratorByRank(long rank, boolean revers) {
        return new ZSkipListRankIterator(rank,revers);
    }

    @Override
    public long length() {
        return this.length;
    }
}
